Un article de Wikipédia, l'encyclopédie libre.
En théorie des nombres , le théorème de Lucas exprime le reste de la division du coefficient binomial
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
par un nombre premier
p
{\displaystyle p}
en termes du développement en base
p
{\displaystyle p}
des entiers
n
{\displaystyle n}
et
k
{\displaystyle k}
.
Le théorème de Lucas a été publié en 1878 par Édouard Lucas [ 1] .
Pour des entiers
n
{\displaystyle n}
et
k
{\displaystyle k}
positifs ou nuls et un nombre premier
p
{\displaystyle p}
, on a la relation de congruence suivante :
(
n
k
)
≡
∏
i
=
0
r
(
n
i
k
i
)
(
mod
p
)
,
{\displaystyle {\binom {n}{k}}\equiv \prod _{i=0}^{r}{\binom {n_{i}}{k_{i}}}{\pmod {p}},}
où
n
=
n
r
p
r
+
n
r
−
1
p
r
−
1
+
⋯
+
n
1
p
+
n
0
,
{\displaystyle n=n_{r}p^{r}+n_{r-1}p^{r-1}+\cdots +n_{1}p+n_{0},}
et
k
=
k
r
p
r
+
k
r
−
1
p
r
−
1
+
⋯
+
k
1
p
+
k
0
{\displaystyle k=k_{r}p^{r}+k_{r-1}p^{r-1}+\cdots +k_{1}p+k_{0}}
sont les développements respectifs de
n
{\displaystyle n}
et
k
{\displaystyle k}
en base
p
{\displaystyle p}
.
Un coefficient binomial
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
est divisible par un nombre premier
p
{\displaystyle p}
si et seulement si au moins un chiffre
k
i
{\displaystyle k_{i}}
de
k
{\displaystyle k}
en base
p
{\displaystyle p}
est strictement plus grand que le chiffre correspondant
n
i
{\displaystyle n_{i}}
de
n
{\displaystyle n}
, auquel cas
(
n
i
k
i
)
=
0
{\displaystyle {\binom {n_{i}}{k_{i}}}=0}
. Ce corollaire est aussi un corollaire du théorème de Kummer .
Démonstration utilisant la formule du binôme [ modifier | modifier le code ]
Cette démonstration est due à Nathan Fine qui l'a publiée en 1947[ 2] .
Si
p
{\displaystyle p}
est un nombre premier, la formule du pion montre que
(
p
k
)
{\displaystyle {\binom {p}{k}}}
est multiple de
p
{\displaystyle p}
pour
1
⩽
k
⩽
n
{\displaystyle 1\leqslant k\leqslant n}
et que donc
(
1
+
X
)
p
≡
1
+
X
p
(
mod
p
)
.
{\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.}
Par récurrence, on en déduit que pour tout entier naturel
i
{\displaystyle i}
:
(
1
+
X
)
p
i
≡
1
+
X
p
i
(
mod
p
)
.
{\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}
Connaissant
n
=
∑
i
=
0
r
n
i
p
i
{\displaystyle n=\sum _{i=0}^{r}n_{i}p^{i}}
et
k
=
∑
i
=
0
r
k
i
p
i
{\displaystyle k=\sum _{i=0}^{r}k_{i}p^{i}}
, on peut écrire :
∑
k
=
0
n
(
n
k
)
X
k
=
(
1
+
X
)
n
=
∏
i
=
0
r
(
(
1
+
X
)
p
i
)
n
i
≡
∏
i
=
0
r
(
1
+
X
p
i
)
n
i
=
∏
i
=
0
r
(
∑
k
i
=
0
n
i
(
n
i
k
i
)
X
k
i
p
i
)
=
∏
i
=
0
r
(
∑
k
i
=
0
p
−
1
(
n
i
k
i
)
X
k
i
p
i
)
=
∑
k
=
0
n
(
∏
i
=
0
r
(
n
i
k
i
)
)
X
k
(
mod
p
)
,
{\displaystyle {\begin{aligned}\sum _{k=0}^{n}{\binom {n}{k}}X^{k}&=(1+X)^{n}=\prod _{i=0}^{r}\left((1+X)^{p^{i}}\right)^{n_{i}}\\&\equiv \prod _{i=0}^{r}\left(1+X^{p^{i}}\right)^{n_{i}}=\prod _{i=0}^{r}\left(\sum _{k_{i}=0}^{n_{i}}{\binom {n_{i}}{k_{i}}}X^{k_{i}p^{i}}\right)\\&=\prod _{i=0}^{r}\left(\sum _{k_{i}=0}^{p-1}{\binom {n_{i}}{k_{i}}}X^{k_{i}p^{i}}\right)=\sum _{k=0}^{n}\left(\prod _{i=0}^{r}{\binom {n_{i}}{k_{i}}}\right)X^{k}{\pmod {p}},\end{aligned}}}
D'où le résultat.
↑ [lire en ligne ] :
Edouard Lucas , « Théorie des Fonctions Numériques Simplement Périodiques », Amer. J. Math. , vol. 1, no 2, 1878 , p. 184-196 (DOI 10.2307/2369308 ) lien Math Reviews (part 1) ;
Edouard Lucas , « Théorie des Fonctions Numériques Simplement Périodiques », Amer. J. Math. , vol. 1, no 3, 1878 , p. 197-240 (DOI 10.2307/2369311 ) lien Math Reviews (part 2) ;
Edouard Lucas , « Théorie des Fonctions Numériques Simplement Périodiques », Amer. J. Math. , vol. 1, no 4, 1878 , p. 289-321 (DOI 10.2307/2369373 ) lien Math Reviews (part 3).
↑ Nathan Fine , « Binomial coefficients modulo a prime », American Mathematical Monthly , vol. 54, no 10, 1947 , p. 589–592 (DOI 10.2307/2304500 , JSTOR 2304500 )